#include <iostream>
#include <string>
#include <map>
#include <memory>
#include <vector>
#include <stack>

using namespace std;

class Trie {
    struct Node{
        Node(char v = char(), int f = int())
            :val(v), freqs(f){}
        char val;
        int freqs;
        map<char, shared_ptr<Node>> childs;
    };
    shared_ptr<Node> root_;
public:
    Trie() {
        root_ = make_shared<Node>();
    }
    
    void insert(string word) {
       shared_ptr<Node> node = root_;
       for(int i{}; i < word.size(); i++){
            if(!node->childs.contains(word[i])){
                node->childs[word[i]] = make_shared<Node>(word[i]);
            }
            node = node->childs[word[i]];
       } 
       node->freqs++;
    }
    
    bool search(string word) {
        shared_ptr<Node> node = root_;
        for(int i{}; i < word.size(); i++){
            if(node->childs.contains(word[i])){
                node = node->childs[word[i]];
            }else{
                return false;
            }
        }

        return node->freqs > 0;
    }
    
    bool startsWith(string prefix) {
        shared_ptr<Node> node = root_;
        for(char ch: prefix){
            if(node->childs.contains(ch)){
                node = node->childs[ch];
            }else{
                return false;
            }
        }

        return true;
    }

    void foreach()
    {
        string word;
        vector<string> words;
        foreach(root_, word, words);
        for(auto elm: words){
            cout << elm << endl;
        }
    }

private:
    // 递归的方式实现
    /* void foreach(shared_ptr<Node> node, string word, vector<string> &words)
    {
        // V L R
        if(node != root_){
            word.push_back(node->val);
            if(node->freqs > 0){
                words.emplace_back(word);
            }
        }

        for(auto elm: node->childs){
            foreach(elm.second, word, words);
        }
    } */

    void pushElm(stack<pair<shared_ptr<Node>, int>> &stk, shared_ptr<Node> node, int len)
    {
        for(auto iter = node->childs.rbegin(); iter != node->childs.rend(); iter++){
            stk.push({iter->second, len});
        }
    }

    void foreach(shared_ptr<Node> node, string word, vector<string> &words)
    {
        stack<pair<shared_ptr<Node>, int>> stk;
        pair<shared_ptr<Node>, int> top;
        pushElm(stk, node, word.size()); 
        while(!stk.empty()){
            top = stk.top();
            stk.pop();

            word.resize(top.second);
            word += top.first->val;

            if(top.first->freqs > 0){
                words.emplace_back(word);
            }

            pushElm(stk, top.first, word.size());
        }
    }

public:

    void queryByPrefix(string prefix)    
    {
        shared_ptr<Node> node = root_;
        vector<string> words;
        string word;
        for(char ch: prefix){
            if(node->childs.contains(ch)){
                node = node->childs[ch];
                word += ch;
            }else{
                throw "no such prefix string";
            }
        }

        // 如果当前前缀刚好是一个存储的单词，直接添加进去
        if(node->freqs > 0)        
            words.emplace_back(word);

        foreach(node, word, words);
        for(auto elm: words){
            cout << elm << endl;
        }
    }

    void remove(string word)
    {
        shared_ptr<Node> node = root_;
        shared_ptr<Node> del = node;
        char delch = node->val;
        for(char ch: word){
            // 记录要删除字符串前缀的路径上，不能删除的数据（包含多个字符串的公共前缀）
            if(node->freqs > 0 || node->childs.size() > 1){
                del = node;
                delch = ch;
            }

            if(node->childs.contains(ch)){
                node = node->childs[ch];
            }else{
                return;
            }

        }

        // 如果当前要删除的节点的有其他字符的前缀，就不删除，将freqs置 1 ，逻辑删除，否则erase
        if(node->childs.empty()){
            del->childs.erase(delch);
        }else{
            node->freqs = 0;
        }
    }

    /* void pushElm(stack<pair<shared_ptr<Node>, string>> &stk, shared_ptr<Node> node, string parent)
    {
        for(auto iter = node->childs.rbegin(); iter != node->childs.rend(); iter++){
            stk.push({iter->second, parent});
        }
    }

    void foreach(shared_ptr<Node> node, string word, vector<string> &words)
    {
        stack<pair<shared_ptr<Node>, string>> stk;
        pair<shared_ptr<Node>, string> top;
        pushElm(stk, node, ""); 
        while(!stk.empty()){
            top = stk.top();
            stk.pop();

            string parent = top.second;
            string cur = top.second + top.first->val;

            if(top.first->freqs > 0){
                words.emplace_back(cur);
                if(words.size() == 3)
                    break;
            }

            pushElm(stk, top.first, cur);
        }
    } */
};

int main(int argc, char const *argv[])
{
    Trie trie;    
    trie.insert("hello"); 
    trie.insert("helloworld"); 
    trie.insert("hellominiword"); 
    trie.insert("hi"); 
    trie.insert("hello"); 
    trie.insert("hiboy"); 
    trie.remove("hi"); 

    trie.foreach();
    cout << "-------------" << endl;
    trie.queryByPrefix("hi");
    return 0;
}
